package pers.qianyu.month_202012.date_20201221.LFU;

import java.util.*;

/**
 * 460. LFU 缓存
 * https://leetcode-cn.com/problems/lfu-cache/
 *
 * @author mizzle rain
 * @date 2020年12月21日21:47:39
 */
public class LFUCache2 {
    // 复杂度为 O (1) 的方法
    private HashMap<Integer, Integer> keyToValue = new HashMap<>();
    private HashMap<Integer, Integer> keyToFreq = new HashMap<>();
    private HashMap<Integer, LinkedHashSet<Integer>> freqToKeyList = new HashMap<>();
    private int minFreq = 0;
    private int cap;

    public LFUCache2(int capacity) {
        this.cap = capacity;
    }

    public int get(int key) {
        Integer value = keyToValue.get(key);
        if (value == null) {
            return -1;
        }
        increment(key);
        return value;
    }

    public void put(int key, int value) {
        // 如果容量为 0 的话，直接返回
        if (cap == 0) {
            return;
        }
        if (keyToValue.containsKey(key)) {
            // 如果存在
            keyToValue.put(key, value);
            increment(key);
            return;
        }
        if (cap == keyToValue.size()) {
            remove();
        }
        keyToValue.put(key, value);
        keyToFreq.put(key, 1);
        freqToKeyList.putIfAbsent(1, new LinkedHashSet<>());
        freqToKeyList.get(1).add(key);
        // 插入一个之后，最小的频率肯定是 1
        minFreq = 1;
    }

    private void increment(int key) {
        Integer freq = keyToFreq.get(key);
        keyToFreq.put(key, freq + 1);
        freqToKeyList.get(freq).remove(key);

        freqToKeyList.putIfAbsent(freq + 1, new LinkedHashSet<>());
        freqToKeyList.get(freq + 1).add(key);

        if (freqToKeyList.get(freq).isEmpty()) {
            freqToKeyList.remove(freq);
            // 如果移除的正好是最少的，就更新最小的
            if (freq == minFreq) {
                minFreq = freq + 1;
            }
        }
    }

    private void remove() {
        LinkedHashSet<Integer> s1 = freqToKeyList.get(minFreq);
        Integer deletedKey = s1.iterator().next();
        s1.remove(deletedKey);
        if (s1.isEmpty()) {
            freqToKeyList.remove(minFreq);
        }
        keyToFreq.remove(deletedKey);
        keyToValue.remove(deletedKey);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */